package com.dragon.modules.yuegou.web;

import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.NoSuchElementException;
import java.util.Objects;
import java.util.Queue;
import java.util.function.BiPredicate;
import java.util.function.Predicate;

/**
 * 使用LinkedList存储子节点实现的Tree
 * 
 * @author liuwu
 * @date 2018年3月7日
 *
 * @param <E>
 */
public class LinkedTree<E> extends AbstractTree<E> implements Cloneable, Tree<E> {

	/**
	 * 根节点
	 */
	private InternalNode<E> root;

	/**
	 * 构造一颗空树
	 */
	public LinkedTree() {
		this.root = null;
	}

	/**
	 * 构造一个以{@code root}为根的树
	 * 
	 * @param root 根节点元素
	 */
	public LinkedTree(E root) {
		Objects.requireNonNull(root);
		this.root = new LinkedNode<>(root);
	}

	/**
	 * 根据一颗树构造一颗新树, 对新树结构的调整不会影响到原树, 反之亦然.
	 * 
	 * @param tree
	 */
	public LinkedTree(Tree<E> tree) {
		Objects.requireNonNull(tree);
		this.root = LinkedNode.copyFrom(tree);
	}

	@Override
	public boolean add(E root) {
		Objects.requireNonNull(root);
		if (this.root == null) {
			this.root = new LinkedNode<>(root);
			return true;
		}
		return false;
	}

	@Override
	public boolean add(E child, E parent) {
		Objects.requireNonNull(child);
		Objects.requireNonNull(parent);
		InternalNode<E> node = this.root.get(parent);
		if (node == null) {
			return false;
		}
		node.addChild(child);
		return true;
	}

	@Override
	public boolean addAll(Collection<? extends E> childs, E parent) {
		Objects.requireNonNull(childs);
		Objects.requireNonNull(parent);
		InternalNode<E> node = this.root.get(parent);
		if (node == null || childs.isEmpty()) {
			return false;
		}
		for (E e : childs) {
			Objects.requireNonNull(e);
			node.addChild(e);
		}
		return true;
	}

	@Override
	public TreeIterator<E> treeIterator(IteratorStrategy strategy) {
		return new ElementIterator<>(this.root, strategy);
	}

	@Override
	public int size() {
		return this.root != null ? this.root.size() : 0;
	}

	@Override
	public int depth() {
		return this.root != null ? this.root.depth() : 0;
	}

	@Override
	public boolean isEmpty() {
		return this.root == null;
	}

	@Override
	public void clear() {
		if (this.root == null) {
			return;
		}
		this.root.remove();
		this.root = null;
	}

	@Override
	public boolean remove(Object o) {
		if (this.root == null) {
			return false;
		}
		InternalNode<E> node = this.root.get(o);
		return remove0(node);
	}

	@Override
	public boolean replace(E old, E element) {
		Objects.requireNonNull(old);
		Objects.requireNonNull(element);
		InternalNode<E> node = this.root.get(old);
		if (node == null) {
			return false;
		}
		node.set(element);
		return true;
	}

	@Override
	public boolean move(E element, E parent) {
		Objects.requireNonNull(element);
		Objects.requireNonNull(parent);
		InternalNode<E> childNode = this.root.get(element);
		if (childNode == null) {
			return false;
		}
		InternalNode<E> parentNode = this.root.get(parent);
		if (parentNode == null) {
			return false;
		}
		// 如果childNode与parentNode是同一个节点, 或childNode是parentNode的父节点, 则无法进行移动操作.
		InternalNode<E> p = parentNode;
		while (p != null) {
			if (p == childNode) {
				return false;
			}
			p = p.parent();
		}
		childNode.remove();
		parentNode.add(childNode);
		return true;
	}

	@Override
	public Node<E> root() {
		return this.root;
	}

	@Override
	public void root(E e) {
		Objects.requireNonNull(e);
		if (this.root == null) {
			this.root = new LinkedNode<>(e);
		} else {
			this.root.set(e);
		}
	}

	@Override
	public boolean addTree(Tree<E> tree, E parent) {
		Objects.requireNonNull(tree);
		Objects.requireNonNull(parent);
		if (tree.isEmpty()) {
			return false;
		}
		InternalNode<E> node = this.root.get(parent);
		if (node == null) {
			return false;
		}
		node.add(LinkedNode.copyFrom(tree));
		return true;
	}

	/**
	 * 移除节点
	 * 
	 * @param node 节点
	 */
	private boolean remove0(InternalNode<E> node) {
		if (node == null) {
			return false;
		}
		node.remove();
		if (node == this.root) {
			this.root = null;
		}
		return true;
	}

	@Override
	public Tree<E> cut(Object element) {
		LinkedTree<E> tree = new LinkedTree<>();
		InternalNode<E> node = get(element);
		if (node != null) {
			remove0(node);
			tree.root.add(node);
		}
		return tree;
	}

	@Override
	public InternalNode<E> get(Object element) {
		return this.root != null ? this.root.get(element) : null;
	}

	@Override
	public Tree<E> subTree(Object element) {
		LinkedTree<E> tree = new LinkedTree<>();
		tree.root = get(element);
		return tree;
	}

	/**
	 * Returns a shallow copy of this <tt>LinkedTree</tt> instance. (The elements
	 * themselves are not copied.)
	 *
	 * @return a clone of this <tt>LinkedTree</tt> instance
	 */
	@Override
	public LinkedTree<E> clone() {
		LinkedTree<E> tree = new LinkedTree<>();
		if (this.root != null) {
			tree.root = LinkedNode.copyFrom(this);
		}
		return tree;
	}

	/**
	 * 
	 * @author liuwu
	 * @date 2018年3月6日
	 *
	 * @param <E>
	 */
	static interface InternalNode<E> extends Node<E> {

		/**
		 * 父节点
		 */
		InternalNode<E> parent();

		/**
		 * 获取某一层的父节点{@code parent(0) == parent()}
		 * 
		 * @param level
		 * @return
		 */
		default InternalNode<E> parent(int level) {
			InternalNode<E> p = parent();
			for (int i = 0; i < level; i++) {
				if (p == null) {
					throw new IndexOutOfBoundsException("level : " + level);
				}
				p = p.parent();
			}
			return p;
		}

		/**
		 * 设置父节点
		 * 
		 * @param parent 父节点
		 */
		void setParent(InternalNode<E> parent);

		/**
		 * 子节点列表
		 * 
		 * @return child node list, 此列表可进行更新操作
		 */
		LinkedList<InternalNode<E>> childs0();

		/**
		 * 内部遍历器
		 * 
		 * @return Iterator for InternalTreeNode
		 */
		Iterator<InternalNode<E>> internalIterator(IteratorStrategy strategy);

		/**
		 * 设置节点大小(节点树的节点总数量)<br>
		 * 
		 * <p>
		 * 如果{@link #size()}的实现方式是临时计算, 则此方法应该什么都不做
		 * 
		 * @param size 大小
		 */
		void setSize(int size);

		/**
		 * 设置节点深度<br>
		 * 
		 * <p>
		 * 如果{@link #depth()}的实现方式是临时计算, 则此方法应该什么都不做
		 * 
		 * @param depth 深度
		 */
		void setDepth(int depth);

		/**
		 * 更新此节点(及其父节点, 递归)的size,增加一个增量.
		 * 
		 * <p>
		 * 如果{@link #size()}的实现方式是临时计算, 则此方法应该什么都不做
		 * 
		 * @param increase 增量
		 */
		default void sizePlus(int increase) {
			InternalNode<E> p = this;
			do {
				p.setSize(p.size() + increase);
				p = p.parent();
			} while (p != null);
		}

		/**
		 * 
		 * <p>
		 * 如果{@link #depth()}的实现方式是临时计算, 则此方法应该什么都不做
		 * 
		 * @param increase
		 */
		default void depthPlus(int increase) {
			depthPlus(increase, true);
		}

		default void depthPlus(int increase, boolean includeSelf) {
			Iterator<InternalNode<E>> itr = internalIterator(IteratorStrategy.BREADTH_FIRST);
			if (!includeSelf) {
				itr.next();
			}
			while (itr.hasNext()) {
				InternalNode<E> node = itr.next();
				node.setDepth(node.depth() + increase);
			}
		}

		/**
		 * {@inheritDoc}
		 * 
		 * @implSpec 本实现允许传入{@code null}元素, 传入{@code null}会查找第一个值为{@code null}的节点.
		 */
		default InternalNode<E> get(Object element) {
			Iterator<InternalNode<E>> itr = internalIterator(IteratorStrategy.BREADTH_FIRST);
			if (element == null) {
				while (itr.hasNext()) {
					InternalNode<E> node = itr.next();
					if (node.element() == null) {
						return node;
					}
				}
			} else {
				while (itr.hasNext()) {
					InternalNode<E> node = itr.next();
					if (element.equals(node.element())) {
						return node;
					}
				}
			}
			return null;
		}

		/**
		 * 移除自身
		 */
		default void remove() {
			if (parent() == null) {
				return;
			}
			Iterator<? extends InternalNode<E>> itr = parent().childs0().iterator();
			while (itr.hasNext()) {
				if (itr.next() == this) {
					itr.remove();
					break;
				}
			}
			parent().sizePlus(-this.size());
		}

		default void clear() {
			if (childs0().isEmpty()) {
				return;
			}
			childs0().clear();
			sizePlus(1 - this.size());
		}

		/**
		 * 向此节点添加一个孩子节点
		 * 
		 * @param child 孩子节点
		 */
		default void add(InternalNode<E> child) {
			childs0().add(child);
			child.setParent(this);
			this.sizePlus(child.size());
			// child.depth + (this.depth + 1 - child.depth) -> this.depth + 1
			child.depthPlus(this.depth() + 1 - child.depth());
		}

		/**
		 * 向此节点添加一个孩子节点
		 * 
		 * @param child 孩子节点
		 * @param index 直接子节点列表中的下标
		 * @throws IndexOutOfBoundsException if the index is out of range
		 *                                   (<tt>index &lt; 0 || index &gt; childs().size()</tt>)
		 */
		default void add(InternalNode<E> child, int index) {
			childs0().add(index, child);
			child.setParent(this);
			sizePlus(child.size());
			child.depthPlus(this.depth() + 1 - child.depth());
		}

		default void sort(Comparator<E> comparator) {
			childs0().sort((InternalNode<E> o1, InternalNode<E> o2) -> comparator.compare(o1.element(), o2.element()));
		}

		default boolean removeChildAt(int index) {
			childs0().get(index).remove();
			return true;
		}
	}

	static class WrappedNode<E> implements InternalNode<E> {

		InternalNode<E> parent;

		final InternalNode<E> node;

		public WrappedNode(InternalNode<E> node) {
			this.node = node;
		}

		@Override
		public E element() {
			return node.element();
		}

		@Override
		public List<Node<E>> childs() {
			return node.childs();
		}

		@Override
		public void set(E element) {
			node.set(element);
		}

		@Override
		public void addChild(E element) {
			node.addChild(element);
		}

		@Override
		public void addChild(E element, int index) {
			node.addChild(element, index);
		}

		@Override
		public Iterator<Node<E>> iterator(IteratorStrategy strategy) {
			return node.iterator(strategy);
		}

		@Override
		public InternalNode<E> parent() {
			return parent;
		}

		@Override
		public void setParent(InternalNode<E> parent) {
			this.parent = parent;
		}

		@Override
		public LinkedList<InternalNode<E>> childs0() {
			return node.childs0();
		}

		@Override
		public Iterator<InternalNode<E>> internalIterator(IteratorStrategy strategy) {
			return node.internalIterator(strategy);
		}

		@Override
		public void setSize(int size) {
			int increase = size - node.size();
			node.setSize(size);
			// 传递
			if (parent != null) {
				parent.sizePlus(increase);
			}
		}

		@Override
		public void setDepth(int depth) {
			node.setDepth(depth);
		}

		@Override
		public int depth() {
			return node.depth();
		}

		@Override
		public int size() {
			return node.size();
		}

		@Override
		public void clear() {
			node.clear();
		}

	}

	static class LinkedNode<E> implements InternalNode<E> {

		InternalNode<E> parent;

		E element;

		final LinkedList<InternalNode<E>> childs0;

		final List<Node<E>> childs;

		int size;

		int depth;

		LinkedNode(E element) {
			this.element = element;
			this.childs0 = new LinkedList<>();
			this.childs = Collections.unmodifiableList(this.childs0);
			this.size = 1;
			this.depth = 0;
		}

		@Override
		public int size() {
			return size;
		}

		@Override
		public int depth() {
			return depth;
		}

		@Override
		public E element() {
			return element;
		}

		@Override
		public InternalNode<E> parent() {
			return parent;
		}

		@Override
		public List<Node<E>> childs() {
			return childs;
		}

		@Override
		public LinkedList<InternalNode<E>> childs0() {
			return childs0;
		}

		@Override
		public void set(E element) {
			Objects.requireNonNull(element);
			this.element = element;
		}

		@Override
		public void setSize(int size) {
			this.size = size;
		}

		@Override
		public void setDepth(int depth) {
			this.depth = depth;
		}

		@Override
		public void setParent(InternalNode<E> parent) {
			this.parent = parent;
		}

		@Override
		public void addChild(E element) {
			this.add(new LinkedNode<>(element));
		}

		@Override
		public void addChild(E element, int index) {
			this.add(new LinkedNode<>(element), index);
		}

		@Override
		public Iterator<InternalNode<E>> internalIterator(IteratorStrategy strategy) {
			return new InternalNodeIterator<>(this, strategy);
		}

		@Override
		public Iterator<Node<E>> iterator(IteratorStrategy strategy) {
			return new NodeIterator<>(this, strategy);
		}

		/**
		 * 根据一颗树构造一个节点树
		 * 
		 * @param tree 树
		 * @return 节点, 如果树为空, 则返回{@code null}
		 */
		static <E> InternalNode<E> copyFrom(Tree<E> tree) {
			if (tree.isEmpty()) {
				return null;
			}
			TreeIterator<E> itr = tree.treeIterator(IteratorStrategy.DEPTH_FIRST);
			InternalNode<E> copy = new LinkedNode<>(itr.next());
			InternalNode<E> current = copy;
			while (itr.hasNext()) {
				E next = itr.next();
				InternalNode<E> node = new LinkedNode<>(next);
				// 遍历节点与当前引用节点的高度差
				int h = itr.depth() - current.depth();
				if (h < 0) {
					// 回溯
					InternalNode<E> parent = current.parent(-h);
					parent.add(node);
				} else if (h == 0) {
					// 平级, 添加兄弟节点
					current.parent().add(node);
				} else if (h == 1) {
					// 更深一层, 添加子节点
					current.add(node);
				} else {
					// impossible
				}
				current = node;
			}
			return copy;
		}
	}

	/**
	 * 入列策略
	 * 
	 * @author liuwu
	 * @date 2018年3月6日
	 *
	 */
	enum InqueueStrategy {

		BREADTH_FIRST() {
			@Override
			<E> void inqueue(LinkedList<InternalNode<E>> queue, InternalNode<E> lastRet) {
				queue.addAll(lastRet.childs0());
			}

		},

		DEPTH_FIRST() {
			@Override
			<E> void inqueue(LinkedList<InternalNode<E>> queue, InternalNode<E> lastRet) {
				Iterator<? extends InternalNode<E>> itr = lastRet.childs0().descendingIterator();
				while (itr.hasNext()) {
					queue.addFirst(itr.next());
				}
			}

		},

		DESCENDING_BREADTH_FIRST() {
			@Override
			<E> void inqueue(LinkedList<InternalNode<E>> queue, InternalNode<E> lastRet) {
				Iterator<? extends InternalNode<E>> itr = lastRet.childs0().descendingIterator();
				while (itr.hasNext()) {
					queue.addLast(itr.next());
				}
			}

		},

		DESCENDING_DEPTH_FIRST() {
			@Override
			<E> void inqueue(LinkedList<InternalNode<E>> queue, InternalNode<E> lastRet) {
				for (InternalNode<E> node : lastRet.childs0()) {
					queue.addFirst(node);
				}
			}
		};

		/**
		 * 入列
		 * 
		 * @param queue   队列
		 * @param lastRet 上一个返回的节点
		 */
		abstract <E> void inqueue(LinkedList<InternalNode<E>> queue, InternalNode<E> lastRet);

	}

	abstract static class AbstractTreeIterator<T, E> implements TreeIterator<T> {

		final LinkedList<InternalNode<E>> queue;

		InternalNode<E> lastRet;

		final InqueueStrategy strategy;

		final int depth;

		boolean skipChilds;

		AbstractTreeIterator(InternalNode<E> root, IteratorStrategy strategy) {
			this.queue = new LinkedList<>();
			this.strategy = impl(strategy);
			this.skipChilds = false;
			if (root != null) {
				depth = root.depth();
				this.queue.add(root);
			} else {
				depth = 0;
			}
		}

		static InqueueStrategy impl(IteratorStrategy strategy) {
			switch (strategy) {
			case BREADTH_FIRST:
				return InqueueStrategy.BREADTH_FIRST;
			case DEPTH_FIRST:
				return InqueueStrategy.DEPTH_FIRST;
			case DESCENDING_BREADTH_FIRST:
				return InqueueStrategy.DESCENDING_BREADTH_FIRST;
			case DESCENDING_DEPTH_FIRST:
				return InqueueStrategy.DESCENDING_DEPTH_FIRST;
			default:
				throw new IllegalArgumentException("遍历策略未实现 : " + strategy);
			}
		}

		@Override
		public boolean hasNext() {
			return !queue.isEmpty() || (!skipChilds && lastRet != null && lastRet.hasChild());
		}

		/**
		 * 入列
		 * <p>
		 * 如果存在{@code lastRet}的子节点, 则把{@code lastRet}的子节点入列. 不同的遍历方式入列顺序有所区别.
		 */
		protected void inqueue() {
			if (skipChilds) {
				// 如果设置为跳过子节点, 则不让子节点入列
				// 需要从新把跳过子节点选项值为false, 让其它节点可以顺利遍历其子节点
				skipChilds = false;
				return;
			}
			if (lastRet != null && lastRet.hasChild()) {
				strategy.inqueue(queue, lastRet);
			}
		}

		protected InternalNode<E> lastRet() {
			if (lastRet == null) {
				throw new IllegalStateException();
			}
			return lastRet;
		}

		/**
		 * 出列
		 * 
		 * @return
		 */
		protected InternalNode<E> poll() {
			if (queue.isEmpty()) {
				lastRet = null;
				throw new NoSuchElementException();
			}
			lastRet = queue.removeFirst();
			return lastRet;
		}

		/**
		 * 下一个节点
		 * 
		 * @return next node
		 */
		protected InternalNode<E> nextNode() {
			inqueue();
			return poll();
		}

		@Override
		public int depth() {
			// 使用相对深度
			return lastRet().depth() - depth;
		}

		@Override
		public void remove() {
			lastRet().remove();
			lastRet = null;
		}

		@Override
		public Tree<T> cut() {
			throw new UnsupportedOperationException();
		}

		@Override
		public Tree<T> get() {
			throw new UnsupportedOperationException();
		}

		@Override
		public void skipChilds() {
			lastRet();
			this.skipChilds = true;
		}

		@Override
		public void iterateChilds() {
			lastRet();
			this.queue.clear();
		}

		@Override
		public List<T> path() {
			throw new UnsupportedOperationException();
		}

	}

	static class ElementIterator<E> extends AbstractTreeIterator<E, E> {

		ElementIterator(InternalNode<E> root, IteratorStrategy strategy) {
			super(root, strategy);
		}

		@Override
		public void set(E element) {
			lastRet().set(element);
		}

		@Override
		public void sort(Comparator<E> c) {
			lastRet().sort(c);
		}

		@Override
		public E next() {
			if (!hasNext()) {
				throw new NoSuchElementException();
			}
			return nextNode().element();
		}

		@Override
		public Tree<E> cut() {
			lastRet().remove();
			LinkedTree<E> tree = new LinkedTree<>();
			tree.root = lastRet;
			lastRet = null;
			return tree;
		}

		@Override
		public Tree<E> get() {
			lastRet();
			LinkedTree<E> tree = new LinkedTree<>();
			tree.root = lastRet;
			return tree;
		}

		@Override
		public List<E> path() {
			// 不使用node.parents()然后加上当前节点是因为如果当前树是某颗树的子树时, 这样得出来的列表元素个数可能超出预期.
			LinkedList<E> path = new LinkedList<>();
			InternalNode<E> node = lastRet();
			for (int i = 0, size = super.depth() + 1; i < size && node != null; i++) {
				path.addFirst(node.element());
				node = node.parent();
			}
			return path;
		}

		@Override
		public List<E> childs() {
			List<E> list = new LinkedList<>();
			for (InternalNode<E> node : lastRet().childs0()) {
				list.add(node.element());
			}
			return list;
		}

	}

	static class NodeIterator<E> extends AbstractTreeIterator<Node<E>, E> {

		NodeIterator(InternalNode<E> root, IteratorStrategy strategy) {
			super(root, strategy);
		}

		@Override
		public void set(Node<E> node) {
			lastRet().set(node.element());
		}

		@Override
		public void sort(Comparator<Node<E>> c) {
			lastRet().childs0().sort(c);
		}

		@Override
		public Node<E> next() {
			if (!hasNext()) {
				throw new NoSuchElementException();
			}
			return nextNode();
		}

		@Override
		public List<Node<E>> path() {
			LinkedList<Node<E>> path = new LinkedList<>();
			InternalNode<E> node = lastRet();
			for (int i = 0, size = super.depth() + 1; i < size && node != null; i++) {
				path.addFirst(node);
				node = node.parent();
			}
			return path;
		}

		@Override
		public List<Node<E>> childs() {
			return lastRet().childs();
		}
	}

	static class InternalNodeIterator<E> extends AbstractTreeIterator<InternalNode<E>, E> {

		InternalNodeIterator(InternalNode<E> root, IteratorStrategy strategy) {
			super(root, strategy);
		}

		@Override
		public void set(InternalNode<E> node) {
			lastRet().set(node.element());
		}

		@Override
		public void sort(Comparator<InternalNode<E>> c) {
			lastRet().childs0().sort(c);
		}

		@Override
		public InternalNode<E> next() {
			if (!hasNext()) {
				throw new NoSuchElementException();
			}
			return nextNode();
		}

		@Override
		public List<InternalNode<E>> path() {
			LinkedList<InternalNode<E>> path = new LinkedList<>();
			InternalNode<E> node = lastRet();
			for (int i = 0, size = super.depth() + 1; i < size && node != null; i++) {
				path.addFirst(node);
				node = node.parent();
			}
			return path;
		}

		@Override
		public List<InternalNode<E>> childs() {
			return lastRet().childs0();
		}
	}

	/**
	 * 把一个集合组织成一颗树.
	 * 
	 * <p>
	 * 例:
	 * 
	 * <pre>
	 * Tree<E> tree = LinkedTree.build(c, e -> e.isRoot(), (e, p) -> e.parent().equals(p));
	 * </pre>
	 * 
	 * @param c               集合, 元素的集合. 要求元素之间能够通过某种方式表达它们的组织结构 (比如所有元素都有id,
	 *                        和parentId属性) , 要求集合中的元素不多不少恰好能够完全组织成一颗树.
	 * @param rootPredicate   根节点断言函数, 如果元素是根则返回true, 集合中必须有且仅有一个根, 否则无法构造成树.
	 * @param parentPredicate 直接父子关系断言函数, 如果函数的第二个参数是第一个参数 的直接父节点则返回true, 否则返回false.
	 * @param comparator      比较排序器, 可空
	 * 
	 * @return tree
	 */
	public static <E> LinkedTree<E> build(Collection<E> c, Predicate<E> rootPredicate,
			BiPredicate<E, E> parentPredicate, Comparator<E> comparator) {
		if (c.isEmpty()) {
			return new LinkedTree<>();
		}
		LinkedList<E> list = new LinkedList<>(c);
		E rootElement = removeRoot(list, rootPredicate);
		LinkedTree<E> tree = new LinkedTree<>(rootElement);

		Queue<InternalNode<E>> queue = new LinkedList<>();
		queue.add(tree.root);
		while (!queue.isEmpty()) {
			InternalNode<E> current = queue.poll();
			for (Iterator<E> it = list.iterator(); it.hasNext();) {
				E e = it.next();
				if (parentPredicate.test(e, current.element())) {
					InternalNode<E> child = new LinkedNode<>(e);
					current.add(child);
					queue.add(child);
					it.remove();
				}
			}
			if (comparator != null) {
				current.sort(comparator);
			}

		}
		if (!list.isEmpty()) {
			throw new IllegalArgumentException("muti-root is not support");
		}

		return tree;
	}

	private static <E> E removeRoot(List<E> list, Predicate<E> rootPredicate) {
		Iterator<E> itr = list.iterator();
		while (itr.hasNext()) {
			E e = itr.next();
			if (rootPredicate.test(e)) {
				itr.remove();
				return e;
			}
		}
		throw new IllegalArgumentException("root not found");
	}
}
